from typing import List


class Solution:
    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        x, y = 0, 0  # 当前圈左上角坐标

        new = [[0] * n for _ in range(m)]

        while m > 0 and n > 0:
            num = 2 * (m - 1) + 2 * (n - 1)  # 元素个数
            kk = k % num  # 旋转圈数

            # 当前圈所有元素下标
            xx, yy = x, y
            lst = [[xx, yy]]
            for _ in range(n - 1):
                yy += 1
                lst.append([xx, yy])
            for _ in range(m - 1):
                xx += 1
                lst.append([xx, yy])
            for _ in range(n - 1):
                yy -= 1
                lst.append([xx, yy])
            for _ in range(m - 2):
                xx -= 1
                lst.append([xx, yy])

            # 更新当前圈
            for i in range(num):
                x1, y1 = lst[i]
                x2, y2 = lst[(i + kk) % num]
                new[x1][y1] = grid[x2][y2]

            x += 1
            y += 1
            m -= 2
            n -= 2

        return new


if __name__ == "__main__":
    # [[10, 20],
    #  [40, 30]]
    print(Solution().rotateGrid(grid=[[40, 10],
                                      [30, 20]], k=1))

    # [[3,4,8,12],
    #  [2,11,10,16],
    #  [1,7,6,15],
    #  [5,9,13,14]]
    print(Solution().rotateGrid(grid=[[1, 2, 3, 4],
                                      [5, 6, 7, 8],
                                      [9, 10, 11, 12],
                                      [13, 14, 15, 16]], k=2))

    # 自制用例
    print(Solution().rotateGrid(grid=[[1, 2],
                                      [8, 3],
                                      [7, 4],
                                      [6, 5]], k=1))

    print(Solution().rotateGrid(grid=[[1, 2, 3, 4],
                                      [8, 7, 6, 5]], k=1000000001))
